package com.xyhuo.leetcode.december;

import com.xyhuo.leetcode.common.ListNode;

/**
 * 合并两个有序链表
 * https://leetcode.cn/problems/merge-two-sorted-lists/
 *
 * @time 2023/12/6
 */
public class MergeTwoLists {

//    public static void main(String[] args) {
//        MergeTwoLists mtl = new MergeTwoLists();
//
////        ListNode l1 = new ListNode(1);
////        ListNode l5 = new ListNode(5);
////        ListNode l7 = new ListNode(7);
////        l1.next = l5;
////        l5.next = l7;
////
////        ListNode l2 = new ListNode(2);
////        ListNode l4 = new ListNode(4);
////        ListNode l6 = new ListNode(6);
////        ListNode l8 = new ListNode(8);
////        l2.next = l4;
////        l4.next = l6;
////        l6.next = l8;
//
////        ListNode l01 = new ListNode(1);
////        ListNode l02 = new ListNode(2);
////        ListNode l04 = new ListNode(4);
////        l01.next = l02;
////        l02.next = l04;
////
////        ListNode l11 = new ListNode(1);
////        ListNode l13 = new ListNode(3);
////        ListNode l14 = new ListNode(4);
////        l11.next = l13;
////        l13.next = l14;
//
//        ListNode l01 = new ListNode(1);
//        ListNode l02 = new ListNode(2);
//        ListNode l04 = new ListNode(4);
//        l01.next = l02;
//        l02.next = l04;
//
//        ListNode l15 = new ListNode(5);
//
//        mtl.mergeTwoLists(l01, l15);
//    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (null == list1) {
            return list2;
        }
        if (null == list2) {
            return list1;
        }
        ListNode n1 = list1.val <= list2.val ? list1 : list2;
        ListNode n2 = list1.val <= list2.val ? list2 : list1;
        while (true) {
            if (n1 == null || n2 == null) {
                break;
            }
            if (n1.next == null) {
                n1.next = n2;
                break;
            }
            while (n1.next.val < n2.val) {
                n1 = n1.next;
                if (n1.next == null) {
                    n1.next = n2;
                    return list1.val <= list2.val ? list1 : list2;
                }
            }
            if (n2.next == null) {
                n2.next = n1.next;
                n1.next = n2;
                break;
            }
            ListNode tmp = n2;
            while (true) {
                if (tmp.next != null && tmp.next.val < n1.next.val) {
                    tmp = tmp.next;
                } else {
                    break;
                }
            }
            ListNode n2N = tmp.next;
            tmp.next = n1.next;
            n1.next = n2;
            n1 = tmp.next;
            n2 = n2N;
        }
        return list1.val <= list2.val ? list1 : list2;
    }
}
